class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        // 1.预处理前缀积以及后缀积
        vector<int> f(n), g(n), ret; // f 为前缀积数组，g 为后缀积数组
        f[0] = 1, g[n - 1] = 1;
        for(int i = 1; i < n; i++)
            f[i] = f[i - 1] * nums[i - 1];

        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];

        for(int i = 0; i < n; i++)
            ret.push_back(f[i] * g[i]);
        
        return ret;
    }
};